/*  使用链表实现队列
 *
 *  链表只对头部进行操作的话，时间复杂度都是O(1)
 *  但是要进行删除操作的话得找到被删除位置前一个位置O(n)复杂度
 *  队列头出 尾进，使用原本的队列就效率很低
 *  所以引入头尾指针，头指针(head)队首，尾指针(tail)队尾，可以实现用链表的队列操作十分快速都是O(1)
 *  但是要删除tail元素还是得从头遍历找到前一个O(n-1)
 *
 *  head == tail ==null 队列为空
 *
 */

public class LinkedListQueue<E> implements Queue<E> {

    //LinkList的内部类,只有LinkedList可以访问，不用让客户知道底层是如何实现
    private class Node{
        public E e;
        public Node next;

        public Node(E e , Node next){
            this.e=e;
            this.next=next;
        }

        public Node(E e ){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }

        public String toString(){
            return e.toString();
        }

    }

    private Node head , tail; //头指针(出队位置)和尾指针(入队位置)
    private int size;


    public LinkedListQueue(){
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }


    //入队
    @Override
    public void enqueue(E e){
        //如果tail==null代表队列里面一定是空
        if(tail == null){
            tail = new Node(e);
            head = tail ;
        }else{
            tail.next=new Node(e);
            tail = tail.next;//维护入队的位置
        }

        size++;
    }

    @Override
    public E dequeue(){
        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        Node retNode = head;
        head = head.next;
        retNode.next=null; //让队首元素指向null脱离链表

        //如果出队后，里面没有元素了，tail和head都得为null
        if(head == null)
            tail = null;

        size--;
        return retNode.e;
    }

    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return head.e;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

        Node cur = head;
        while(cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL tail");
        return res.toString();
    }

    public static void main(String[] args){

        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }

}
